package personal.zq.practice.common.utils.leetcode.medium;

import java.util.ArrayList;
import java.util.List;

/**
 * 二维网格迁移
 * 给你一个 m 行 n列的二维网格grid和一个整数k。你需要将grid迁移k次。
 *
 * 每次「迁移」操作将会引发下述活动：*
 * 位于 grid[i][j]的元素将会移动到grid[i][j + 1]。
 * 位于grid[i][n- 1] 的元素将会移动到grid[i + 1][0]。
 * 位于 grid[m- 1][n - 1]的元素将会移动到grid[0][0]。
 * 请你返回k 次迁移操作后最终得到的 二维网格
 *
 * 示例 1：
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
 * 输出：[[9,1,2],[3,4,5],[6,7,8]]
 * 示例2：
 * 输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
 * 输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
 *
 * @author zhangqing
 * @version 1.0
 * @date 2022/7/20
 */
public class ShiftGrid {
    public static void main(String[] args) {
        int[][] in = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

        for (int[] a : in) {
            System.out.print("{");
            for (int i = 0; i < a.length; i++) {
                Integer b = a[i];
                System.out.print(b);
                if (i != a.length - 1) {
                    System.out.print(",");
                }
            }
            System.out.println("}");
        }
        List<List<Integer>> ret = shiftGrid(in, 2);

        System.out.println("迁移后：");
        for (List<Integer> a : ret) {
            System.out.print("{");
            for (int i = 0; i < a.size(); i++) {
                Integer b = a.get(i);
                System.out.print(b);
                if (i != a.size() - 1) {
                    System.out.print(",");
                }
            }
            System.out.println("}");
        }
    }

    /**
     * 一维展开
     * 设 mm 和 nn 分别为网格的行列数，我们将网格 \textit{grid}grid 想象成由多个一维数组 \big \{\textit{grid}[i]; 0 \le i \lt n \big \}{grid[i];0≤i<n} 按顺序拼接而成的一维数组，那么元素 
     * \textit{grid}[i][j]grid[i][j] 在该一维数组的下标为 \textit{index} = i \times n + jindex=i×n+j。
     *
     * 每次迁移操作都相当于将该一维数组向右循环移动一次，那么 kk 次迁移操作之后，元素 \textit{grid}[i][j]grid[i][j] 在该一维数组的下标变为 \textit{index}_1 = (\textit{index} + k) \bmod (m \times 
     * n)index      * 1    * 	     *  =(index+k)mod(m×n)，在网格的位置变为 \textit{grid}[\Big \lfloor \dfrac{\textit{index}_1}{n} \Big \rfloor][\textit{index}_1 \bmod n]grid[⌊
     * n     * index   * 1[index  1   * *  modn]。
     *
     * @param grid
     * @param k
     * @return
     */
    public static List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j < n; j++) {
                row.add(0);
            }
            ret.add(row);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int index1 = (i * n + j + k) % (m * n);
                ret.get(index1 / n).set(index1 % n, grid[i][j]);
            }
        }
        return ret;
    }
}
